package com.zr.utils;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import com.zr.vo.base.BaseCity;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.MalformedURLException;
import java.net.URL;
import java.net.URLConnection;
import java.util.*;


/**
 * @author 陈鹏
 */
public class TransitPathUtil {
    /**
     * 设置无穷大的值为10的七次方
     */
    private static int INF = (int) 1e7;
    /**
     * 设置无无向带权邻接矩阵尺寸
     */
    private static int N = 100;
    /**
     * 地图的无向带权邻接矩阵
     */
    private double[][] g = new double[N][N];
    /**
     * 记录当前路径
     */
    private int[] x = new int[N];
    /**
     * 记录当前最优路径
     */
    private int[] bestx = new int[N];
    /**
     * 当前路径长度
     */
    private double cl;
    /**
     * 当前最短路径长度
     */
    private double bestl;
    /**
     * 城市个数n,边数m
     */
    private int n, m;

    /**
     * 交换函数
     *
     * @param array
     * @param a
     * @param b
     * @author 陈鹏
     */
    private void swap(int array[], int a, int b) {
        int temp;
        temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    /**
     * 计算各路径长度记录最优 线路和最短距离
     *
     * @param t
     * @author 陈鹏
     */
    private void Traveling(int t) {
        //到达叶子节点
        if (t > n) {
            /*
            最后一个城市与住地城市有边相连并且路径长度比当前最优值小，说明找到了一条更好的路径，记录相关信息
             */
            if (g[x[n]][1] != INF && (cl + g[x[n]][1] < bestl)) {
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
                bestl = cl + g[x[n]][1];
            }
        } else {
            //没有到达叶子节点
            //搜索扩展节点的所有分支
            for (int j = t; j <= n; j++) {
                if (g[x[t - 1]][x[j]] != INF && (cl + g[x[t - 1]][x[j]] < bestl)) {
                    //如果第t-1个城市与第t个城市有边相连并且有可能得到更短的路线
                    swap(x, t, j);
                    //交换两个元素的值
                    cl = cl + g[x[t - 1]][x[t]];
                    //从第t+1层的扩展结点继续搜索
                    Traveling(t + 1);
                    //第t+1层搜索完毕，回溯到第t层
                    cl = cl - g[x[t - 1]][x[t]];
                    swap(x, t, j);
                }
            }
        }
    }


    /**
     * 初始化函数
     *
     * @author 陈鹏
     */
    private void init() {
        bestl = INF;
        cl = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                g[i][j] = g[j][i] = INF;
            }
        }
        for (int i = 0; i <= n; i++) {
            x[i] = i;
            bestx[i] = 0;
        }
    }

    /**
     * 打印最短路径和距离
     *
     * @author 陈鹏
     */
    private void print() {
        System.out.print("最短路径");
        for (int i = 1; i <= n; i++) {
            System.out.print(bestx[i] + "---->");
        }
        System.out.println("1");
        System.out.println("最短路径长度：" + bestl);
        System.out.println("*************");
        for (int i = 0; i <= n; i++) {
            System.out.println(Arrays.toString(g[i]));
        }


    }

    /**
     * 传入城市数，连接数，城市间距离二维数组
     *
     * @param cityNum
     * @param roadNum
     * @param distance
     * @return
     * @author 陈鹏
     */
    private String route(int cityNum, int roadNum, double[][] distance) {
        n = cityNum;
        init();
        m = roadNum;
        for (int j = 0; j < m; j++) {
            g[(int) distance[j][0]][(int) distance[j][1]] = g[(int) distance[j][1]][(int) distance[j][0]] = distance[j][2];
        }
        Traveling(2);
        return Arrays.toString(bestx);
    }

    /**
     * 将传入的城市列表转换成城市间距离二维数组
     *
     * @param cityList
     * @return
     * @author 陈鹏
     */
    private double[][] road(List<BaseCity> cityList) {
        int size = 0;
        for (int i = 1; i < cityList.size(); i++) {
            size += (cityList.size() - i);
        }
        double[][] road = new double[size][];
        List<double[]> doubles = new ArrayList<>();
        int i = 0;
        //格式化数据转换成地图api标准请求参数计算距离
        for (; i < cityList.size(); i++) {
            StringBuilder destination = new StringBuilder();
            destination.append(cityList.get(i).getLongitude());
            destination.append(",");
            destination.append(cityList.get(i).getLatitude());
            StringBuilder origins = new StringBuilder();
            for (int j = i + 1; j < cityList.size(); j++) {
                origins.append(cityList.get(j).getLongitude());
                origins.append(",");
                origins.append(cityList.get(j).getLatitude());
                if (j < cityList.size() - 1) {
                    origins.append("|");
                }
            }
            //api地址
            String url = "https://restapi.amap.com/v3/distance?origins=" + origins + "&destination=" + destination + "&key=870a2505da2303f0fd87c9eb66519f01&output=json、";
            String json = loadJSON(url);
            JSONObject obj = JSON.parseObject(json);
            if (obj.get("status").toString().equals("1")) {
                JSONArray jsonArray = obj.getJSONArray("results");
                for (int j = 0; j < jsonArray.size(); j++) {
                    JSONObject objectInArray = jsonArray.getJSONObject(j);
                    double distance = objectInArray.getDouble("distance");
                    double originId = objectInArray.getDouble("origin_id") + 1 + i;
                    doubles.add(new double[]{i + 1, originId, distance});
                }
            }

        }
        for (int k = 0; k < doubles.size(); k++) {
            road[k] = new double[3];
            for (int j = 0; j < 3; j++) {
                road[k][j] = (doubles.get(k))[j];
            }
        }
        return road;
    }

    /**
     * 调用高德距离测算api计算各城市之间的驾车距离
     *
     * @param url
     * @return
     * @author 陈鹏
     */
    private String loadJSON(String url) {
        StringBuilder json = new StringBuilder();
        try {
            URL oracle = new URL(url);
            URLConnection yc = oracle.openConnection();
            BufferedReader in = new BufferedReader(new InputStreamReader(
                    yc.getInputStream()));
            String inputLine = null;
            while ((inputLine = in.readLine()) != null) {
                json.append(inputLine);
            }
            in.close();
        } catch (MalformedURLException e) {
        } catch (IOException e) {
        }
        return json.toString();
    }

    /**
     * 返回最短路径顺序城市列表
     *
     * @param cityList
     * @return
     * @author 陈鹏
     */
    public Map<String, Object> getShortestPathCityList(List<BaseCity> cityList) {
        Map<String, Object> map = new HashMap<>();
        List<BaseCity> shortestPathCityList = new ArrayList<>();
        double[][] roads = road(cityList);
//        计算最短路径顺序
        route(cityList.size(), roads.length, roads);
        for (int i = 0; i < bestx.length; i++) {
            if (bestx[i] != 0) {
                shortestPathCityList.add(cityList.get((bestx[i] - 1)));
            }
        }
        shortestPathCityList.add(cityList.get(bestx[1] - 1));
        map.put("list", shortestPathCityList);
        map.put("distance", bestl);
        return map;
    }
}


